SWERC 2013 F Odd and Even Zeroes

发表于 | 更新于 | 分类于 ， ， | 阅读次数：
本文字数： 1.8k | 阅读时长 ≈ 2 分钟

task

在数学中，一个数n的阶乘写作n!，且定义如下：
$n! = 1 × 2 × 3 × 4 × $• • • $× (n − 1) × n =\prod_{i=1}^N i$
0!被认为是1。n!将会随着n迅速增长。如下一些数的阶乘：
0! = 1 5! = 120
1! = 1 10! = 3628800
2! = 2 14! = 87178291200
3! = 6 18! = 6402373705728000
4! = 24 22! = 1124000727777607680000
通过观察可以发现，有些数的阶乘末尾中有奇数个零(即5！和18！)，而有些数的阶乘的末尾中有偶数个零(即0！，10！，20！)。那么问题来了，给定一个数n，求在1~n中有多少数的阶乘的末尾有偶数个0？
$n<=10^{18}$

solution

首先我们需要知道怎样的数字的阶乘是可以有偶数个零。
肯定是是由偶数个10相乘，而10=2*5，所以我们只用统计2和5的因子的个数，看一下它们是否能够组成偶数个10，那么10的个数一定是根据个数较少的那个因子判定的，而在一个数的阶乘当中因子2的个数总是不少于5的，所以我们就只用统计n的阶乘中5的个数。
那么怎么统计呢？最暴力的写法就是用字母那题的方法判断，一个数我们可以算的很快，但是我们需要1~n的所有的数的阶乘中因子5的个数，而n最大可达$10^{18}$，显然会超时。
原先我想着用数学的方法去写，但是随着想法越来越复杂，只能放弃。
对于判断一个数的阶乘是否有偶数个5，正解有更好的方法：以530为例，我们将其转化为5进制，即4110，而1~530中为5的倍数的数用411(5进制)个，为25的倍数的有41(5进制)个，为125的倍数的有4(5进制)个，那么我们可以发现当411的每一位数字之和为偶数的话，那么1~530中就有偶数个数为5的倍数。25，和125都可以以此类推。
所以接下来我们就可以用数位dp来计算个数了。
$dp[f][p][pre][x]$表示当前数字是第x位时，前面几位上的数字这和的末位的奇偶性为pre，p为前面几位时的pre之和的奇偶性。如果前面有一位的数字是小于n那一位上的数字，那么接下来取什么数字，都将小于n，所以我们需要一个f，来判断当前数字是否可以随便取。
记忆化搜索的边界是但x<0时，只有p=0时，才说明是有偶数个5，我们返回一个1.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <string.h>
#include <algorithm>
#define ll long long
using namespace std;
int num[30];
ll dp[2][2][2][27];
ll dfs(int x,int f,int p,int pre){//x-th digit,have or haven't limit,parity,the sum of pre x digit's parity
	if(x<0)return p==0;
	ll &t=dp[f][p][pre][x];
	if(t==-1){
		t=0;
		if(f){
			for(int i=0;i<=num[x];i++)
				t+=dfs(x-1,i==num[x],(p+pre+i)&1,(pre+i)&1);
		}
		else {
			for(int i=0;i<5;i++)
				t+=dfs(x-1,0,(p+pre+i)&1,(pre+i)&1);
		}
	}return t;
}
ll solve(ll n){
	if(n<5)return n+1;
	int c=0;
	while(n)num[c++]=n%5,n/=5;
	memset(dp,-1,sizeof(dp));
	return dfs(c-1,1,0,0);
}
int main(){
	ll n;
	while(1){
		cin>>n;
		if(n==-1)return 0;
		cout<<solve(n)<<endl;
	}
	return 0;
}